1. Field of the Invention
This invention relates to the field of computer software, and, more specifically, to testing and debugging processes.
Sun, Sun Microsystems, the Sun logo, Java and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
2. Background Art
One step in software development is testing and verification of a product. The software product is typically executed under a variety of conditions, and any faults are reported for subsequent correction. In some software systems, there are extra operations, such as monitoring or xe2x80x9chousekeepingxe2x80x9d subprocesses or routines (e.g., garbage collection), that may be carried out at various points (referred to herein as xe2x80x9ctest pointsxe2x80x9d) in the execution of a process (e.g., an application, program or portion thereof). During ordinary execution, a process may cause or permit execution of these extra operations at any one or more of these test points by intermittently branching to the subprocess handling those extra operations.
Ideally, for exhaustive testing purposes, it is desirable to evaluate the execution of these extra operations at all such test points to verify that each such test point does not have any errors associated with it. However, if executed at every possible test point in a single execution of the main process, these extra operations may entail prohibitive performance cost in the execution of the process or program, particularly for more complicated functions. For example, it may take an inordinate amount of time for a process to execute beyond its initial stages due to frequent branching to a subprocess. Thus, evaluation of test points occurring later in the execution of the main process is undesirably delayed while the earlier portions of the process are exhaustively tested. Also, for time-critical applications, the slow-down in performance may disrupt normal operations, diminishing the effectiveness of such tests.
FIG. 1 is a block diagram illustrating the branching of a main process to a subprocess at one or more test points. Considering an intermittent garbage collection example, executing process 100 represents a program under execution and subprocess 102 represents the system""s garbage collector for recovering unused memory resources. Executing process 100 may be a program running on an underlying virtual machine (VM) or operating system, and may contain one or more threads of execution, each of which may contain a plurality of garbage collection points (gc-points) that can be considered test points. During normal execution, executing process 100 may branch to the garbage collector subprocess 102 at any one (or more) of those gc-points to permit recovery of memory resources. Branching may be explicitly performed via direct or indirect branching instructions in the executing process, or branching may be performed by the release of processor or VM execution control by a currently executing thread to enable the execution of a second thread supporting the subprocess (i.e., via cooperative scheduling).
In FIG. 1, executing process 100 contains M operations or instructions OP A1 through OP A(M), interspersed with test points 1xe2x88x92N. Subprocess 102 contains K operations OP B1 through OP B(K). As indicated by arrow 103, executing process 100 may branch to the first operation OP B1 of subprocess 102 from any test point (e.g., from test point 1) to initiate execution of subprocess 102. When execution of subprocess 102 is completed (i.e., OP BK has been executed), subprocess 102 returns (arrow 104) to the operation (e.g., OP A3) following the test point from which branching occurred.
If branching occurs at only a limited number of the N test points, the impact of executing the extra instructions of subprocess 102 is acceptable. However, if subprocess 102 is executed at each of the N test points in an exhaustive test execution, the total execution time of process 100 may increase substantially for large values of N. Also, the K increases, the interruption and slow-down of process 100 becomes more prohibitive.
One method for reducing the disruptive nature of test point evaluation is to evaluate (e.g., branch to a subprocess) at a subset of the possible test points, selecting those test points to be evaluated based upon a pseudo-random distribution of test points. An irregular sampling of test points is achieved with less performance cost than the exhaustive technique of evaluating every test point. However, not all test points are tested. Even across multiple executions of the process with different pseudo-random distributions of test points, there is no mechanism for ensuring that all test points are ultimately evaluated. Pseudo-random techniques therefore provide only incomplete evaluation results.
The problem associated with evaluating test points are more clearly understood with reference to an example test point situation. For this purpose, the example of an intermittent garbage collection system is described in more detail below.
Garbage collection is an important aspect of memory management in most modern computer systems. Garbage collection (GC) refers to the process of reclaiming portions of main memory that are no longer in use by the system or any running applications. The execution of programs in a computer system is typically interrupted intermittently to permit the garbage collection process to run. Ideally, the frequency of these interruptions is kept low to impact the execution of other programs as little as possible.
In an object-oriented system, for example, garbage collection is typically carried out to reclaim memory allocated to objects and other data structures (e.g., arrays, etc.) that are no longer referenced by an application. The reclaimed memory can then be re-allocated to store new objects or data structures. The garbage collection process may be either conservative or extract. Conservative garbage collection involves scanning memory space for stored values that match the address of an object (or other memory structure) that is being considered for collection. If a matching value is not found in the memory being scanned, then no references to the object exist, and the object may be safely collected. If a matching value is found, it is assumed that the value is a reference (e.g., a pointer) to the object under consideration, and the object is not collected.
In exact garbage collection, only true references (pointers) are considered in a scan, so coincidentally matching data values are ignored in the collection process. This means that an object without any associated references is always considered garbage in a scan, and more efficient collection is achieved. However, to perform exact garbage collection, the scanning process must have reliable information regarding which memory locations contain live references (i.e., active, non-null references). Only those memory locations containing live references are scanned to determine reference matches for objects under consideration for collection.
To provide more efficient use of memory space in terms of compaction, xe2x80x9ccopyingxe2x80x9d garbage collection is commonly implemented. In copying garbage collection, the memory space is divided into regions and an object transfer is performed. When garbage collection is carried out, objects in a portion of memory referred to an xe2x80x9cfromxe2x80x9d space are copied to a portion referred to as xe2x80x9ctoxe2x80x9d space. Those objects in xe2x80x9cfromxe2x80x9d space that are considered xe2x80x9cgarbagexe2x80x9d by the scan process are not copied to xe2x80x9ctoxe2x80x9d space. The process of copying the objects results in reduced fragmentation of the memory space and better compaction.
The process of performing garbage collection, i.e., the steps of scanning memory and collecting unreferenced resources, is a nontrivial task. This is particularly true for copying garbage collection, which can entail many expensive memory transfer operations. If garbage collection is performed at every possible opportunity, as is desired for exhaustive testing, the garbage collection process will cause the execution of the main process or program to be frequently interrupted and undesirably slowed. Yet, thorough testing of the garbage collection process is necessary to ensure proper, noncorrupting memory management.
Garbage collection is also necessary in runtime environments including virtual machines. A virtual machine is a software mechanism that provides a level of abstraction from the instructions implemented by the underlying hardware computer system. The virtual machine typically implements a garbage collector to re-allocate memory for data structures used to support those processes (e.g., programs and supporting processes) executed by the virtual machine.
FIG. 2 illustrates a computer system comprising a virtual machine. The computer system includes computer hardware 310, operating system 309, virtual machine (VM) 305 and multiple executing processes (P1-P6). Computer hardware 310 comprises, for example, a processor, physical memory, and input/output mechanisms.
Hardware 310 supports execution of a particular instruction set based on the given processor architecture (e.g., SPARC, Pentium, etc.). Operating system 309 runs on top of hardware 310, and provides a software foundation of system functions such as file organization, memory management, windows support, etc. Operating system 309 provides an interface to overlying processes which permit those processes to access the system functions through OS calls. Virtual machine 305 executes on top of operating system 309, and provides an execution environment abstracted from the underlying hardware 310. For example, VM 305 may support a different instruction set from that of hardware 310.
In this discussion, a process may be an application program, subroutine, thread or other unit of executable operations. Processes executing within the system of FIG. 2 may execute on top of operating system 309, making use of the execution environment directly supported by operating system 309 and hardware 310, or processes may execute in the environment provided by VM 305. As shown, processes P1-P3 are executed by VM 305, and processes 5-6 are executed on top of operating system 309. Internal processes of VM 305, such as process P4, may be either executed on top of VM 305 (e.g., as interpreted virtual machine code) or in parallel with VM 305 as xe2x80x9cnativexe2x80x9d code of the underlying operating system 309 and hardware 310. For purposes of illustration, an embodiment of a runtime environment implementing a virtual machine is described below.
Object-oriented applications typically comprise one or more object classes and interfaces. In many programming languages, a program is compiled into machine-dependent, executable program code. However, classes may also be written in the a programming language that supports compiling of those classes into machine independent bytecode class files. In a bytecode class file implementation, each class may contain, for example, code and data in a platform-independent format called the class file format. The computer system acting as the execution vehicle contains a program called a virtual machine, which is responsible for executing the code in each class.
Applications may be designed as standalone applications, or as xe2x80x9cappletsxe2x80x9d which are identified by an applet tag in an HTML (hypertext markup language) document, and loaded by a browser application. The class files associated with an application or applet may be stored on the local computing system, or on a server accessible over a network. Each class is loaded into the virtual machine, as needed, by the xe2x80x9cclass loader.xe2x80x9d
The classes of an application or applet are loaded on demand from the network (stored on a server), or from a local file system, when first referenced during the application or applet""s execution. The virtual machine locates and loads each class file, parses the class file format, allocates memory for the class""s various components, and links the class with other already loaded classes. This process makes the code in the class readily executable by the virtual machine.
FIG. 3 illustrates one example of a runtime environment. In the compile environment, a software creates sources files that contain the programmer readable class definitions, including data structures, method implementations and references to other classes. Those source files are provided to a pre-compiler, which compiles the source files into compiled xe2x80x9c.classxe2x80x9d files 302 that contain bytecodes executable by a virtual machine. Bytecode class files 302 are stored (e.g., in temporary or permanent storage) on a server, and are available for download over a network. Alternatively, bytecode class files 302 may be stored locally in a directory on the client platform.
The runtime environment contains a virtual machine 305 which is able to execute bytecode class files and execute native operating system (xe2x80x9cO/Sxe2x80x9d) calls to operating system 309 when necessary during execution. As stated previously, virtual machine 305 provides a level of abstraction between the machine independence of the bytecode classes and the machine-dependent instruction set of the underlying computer hardware 310, as well as the platform-dependent calls of operating system 309.
Class loader and bytecode verifier (xe2x80x9cclass loaderxe2x80x9d) 303 is responsible for loading bytecode class files 302 and supporting class libraries 304 into virtual machine 305 as needed. Class loader 303 also verifies the bytecodes of each class file to maintain proper execution and enforcement of security rules. Within the context of runtime system 308, either an interpreter 306 executes the bytecodes directly, or a xe2x80x9cjust-in-timexe2x80x9d (JIT) compiler 307 transforms the bytecodes into machine code, so that they can be executed by the processor (or processors) in hardware 310.
The runtime system 308 in virtual machine 305 supports a general stack architecture. The manner in which this general stack architecture is supported by the underlying hardware 310 is determined by the particular virtual machine implementation, and reflected in the way the bytecodes are interpreted or JIT-compiled. Other elements of the runtime system include, for example, thread management (e.g., scheduling) mechanisms and the garbage collector.
In the virtual machine, garbage collection is performed to reclaim memory space from a region of memory known as the heap. The heap is used to store objects and arrays that are referenced by pointers stored as local variables in activation records, or xe2x80x9cstack frames,xe2x80x9d of a stack associated with an individual thread of execution in the virtual machine. Threads may be associated with programs being executed by the virtual machine, or with processes of the virtual machine itself. The invocation of a method by a given thread results in the creation of a new stack frame that is xe2x80x9cpushedxe2x80x9d onto the stack of that thread. References to objects on the heap may be removed by an active (i.e., currently executing) method setting the respective pointer to a xe2x80x9cnullxe2x80x9d value, or by removal of a respective stack frame in response to completion of its associated method.
In any thread of execution, there may be many garbage collection points, or xe2x80x9cgc-points,xe2x80x9d where garbage collection can occur. However, actual garbage collection typically takes place at only a fraction of these possible gc-points each time the given thread of execution is run. In virtual machine implementations using a compiler, to facilitate exact garbage collection, the compiler may provide information at each gc-point about the set of locations in the stack frames that contain pointers to objects or arrays. Garbage collection is performed by determining which objects and arrays in the heap are referenced from within the set of locations specified by the compiler, and reclaiming those objects and arrays that are no longer referenced.
Unfortunately, the compiler may have an error (i.e., a xe2x80x9cbugxe2x80x9d) that causes a stack location to be mistakenly omitted from the specified set of pointer locations. This type of compiler bug can result in the reclaiming of an object or array when a reference still exists. Also, for copying garbage collection, this compiler bug may result in a failure to update a pointer reference to point to the appropriate copy of the associated object or array. In either case, future references made to the object or array through the omitted stack location can result in improper execution of an application. It is desirable to determine whether the garbage collector and the compiler are operating correctly at every gc-point. Testing is typically done by executing a program in the virtual machine and observing the behavior of the garbage collector at the gc-points associated with the program.
Stress tests attempt to test a range of execution conditions that will result in the triggering and resulting detection any bugs in the system. However, with respect to garbage collection, a stress test will only result in testing at gc-points where garbage collection actually occurs in the testing program. Because garbage collection occurs at only a subset of gc-points, and because that subset of gc-points may not differ from one execution to the next for a particular application or input data set, stress tests are insufficient to reliably and exhaustively find bugs associated, for example, with the misidentification of a live reference at possibly a single gc-point out of many in the execution of the application. Conditions may be such that the compiler produces errors at untested gc-points. A mechanism is desired which provides exhaustive testing for test point scenarios such as garbage collection without entailing the prohibitive performance costs associated with evaluation of every test point.
A method and apparatus for testing processes in a computer system are described. In a software process, there exist many test points in the execution of the process where stress testing may be applied. Testing every test point in a single execution can be prohibitively slow. In accordance with the invention, the process is executed with stress testing applied at selected test points and test intervals. The selected test points are based on prime numbers and varied for successive execution iterations. An efficient distribution of evaluated test points is achieved, and all possible test points are ultimately evaluated within a small number of execution iterations.
In an embodiment of the invention, the total number of test points is first determined. A first execution run is evaluated at selected test points that correspond to prime numbers greater than the square root of the total number of test points. Subsequent execution iterations are then performed evaluating test points at selected test intervals, where the test intervals for respective execution iterations correspond to prime numbers less than or equal to the square root of the total number of test points. The prime numbers for the selected test intervals are chosen in decreasing order, for example. In another embodiment, the first execution run is performed subsequent to the execution iterations using the selected test intervals.